//单词拆分
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        unordered_set<string>s1(wordDict.begin(),wordDict.end());
        //dp[i] 长度为i的字符串能否被拼成
        vector<bool>dp(s.size()+1,false);
        dp[0]=true;
        for(int i=1;i<=s.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                string str=s.substr(j,i-j);
                if(s1.find(str)!=s1.end() && dp[j]==true)
                dp[i]=true;
            }
        }
        return dp[s.size()];
    }
};
//等差数列划分
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        //dp[i] 以nums[i]结尾的所有子数组中构成等差数列的个数
        //返回dp数组中所有的值即可
        int n=nums.size();
        if(n<3) return 0;
        vector<int>dp(n,0);
        int res=0;
        for(int i=2;i<n;i++)
        {
            int subnum=nums[i-1]-nums[i-2];
            if(nums[i]-nums[i-1]==subnum)
            {
                dp[i]=dp[i-1]+1;
            }
        }
        for(auto e:dp) res+=e;
        return res;

    }
};
//最长湍流子数组
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) 
    {
        //只要一上一下就是湍流子数组 
        //相邻如果相等了 那就湍流子数组就是1
        int n=arr.size();
        vector<int>dp(n,0);
        if(n==1) return 1;
        dp[0]=1;
        if(arr[0]!=arr[1]) dp[1]=2;
        else dp[1]=1;
        int res=dp[1];
        for(int i=2;i<n;i++)
        {
            if(arr[i]>arr[i-1])
            {
                if(arr[i-1] <arr[i-2]) dp[i]=dp[i-1]+1;
                else dp[i]=2;
                
            }
            else if(arr[i]<arr[i-1])
            {
                if(arr[i-1] >arr[i-2]) dp[i]=dp[i-1]+1;
                else dp[i]=2;

            }
            else
            {
                dp[i]=1;
            }
            res=dp[i]>res?dp[i]:res;
        }
        return res;
    }
};